package 剑指offer;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/25 14:43 星期四
 */
public class _24_反转链表 {

    /**
     * 递归写法（根据双指针）
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head) {
        //根据双指针思想，我们必须传递一个头结点cur和一个pre的null
        return reverse(head,null);
    }
    public ListNode reverse(ListNode cur,ListNode pre){
        if (cur == null){
            //当达到结束条件，返回新的头结点，就是cur的前一个结点，也就是pre（所以这里返回pre）
            return pre;
        }
        //定义临时结点，是cur的下一结点
        ListNode temp = cur.next;
        //让cur的next指向前一个节点pre
        cur.next = pre;
        //然后递归，此时cur需要右移到temp，也就是下一次递归需要真正的CUR.next也就是刚存的temp
        //第二个参数其实是pre，那么我们要求pre成为新的cur，所以直接传递pre
        //其实也可以：
        //pre = cur;
        //cur = temp;
        //后，再传递cur和pre：return reverse(temp,cur);
        return reverse(temp,cur);
    }

    /**
     * 双指针解法，每次循环，让cur（pre后面的结点）指向pre（前一结点）
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        //定义双指针，定义cur在头结点（第一个有效结点）上，定义pre，让其永远在cur前面
        //最开始时，cur是第一个有效结点，故pre应当是空指针
        ListNode cur = head;
        ListNode pre = null;
        //当cur为空时，说明遍历结束了
        while (cur != null) {
            //临时指针，保存cur的下一结点（防止cur与next结点断开连接）
            ListNode temp = cur.next;
            //让cur指向前一结点pre
            cur.next = pre;
            //pre成为cur（反转链表头结点右移）
            pre = cur;
            //让cur跳到下一结点（因为cur要永远在pre前面，刚才的cur->pre只是为了赋值给pre，临时而已）
            cur = temp;

        }
        //pre为头结点
        return pre;
    }



    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

}
